package com.computer.fundamentals.datastructure;

import com.computer.util.Constant;
import com.computer.util.UniversalMethod;

public class UnionFindSet {

    public int[] set;

    public int size;

    /**
     * 初始化集合，此刻每个集合自己是自己的父节点
     */
    public UnionFindSet(int size_) {
        this.size = size_;
        this.set = new int[size_];
        for (int i = 0;i < size_;i++) {
            set[i] = i;
        }
    }

    /**
     * 查找集合的顶级父节点
     */
    public int find(int p) {
        while (p != set[p]) {
            p = set[p];
        }
        return p;
    }

    /**
     * 合并同一个父节点的集合，合并规则：
     *      1. 父节点相同，不进行合并，默认为一个集体
     *      2. 将p的父节点设置为q
     */
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) {
            return;
        }

        set[pRoot] = qRoot;
    }

    /**
     * 测试,以LeetCode.990(等式方程的可满足性)为例：
     * ------------------------------------------------------------------------------------------------------------
     * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4
     * 并采用两种不同的形式之一："a==b" 或"a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
     * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回true，否则返回 false。
     *
     * 示例：
     * 输入：["a==b","b!=a"]
     * 输出：false
     * 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
     *
     * 注意：
     * 1. 等式均由小写字母、等号及不等号组成
     * 2. 等式和不等式的区分点在equation[1]的位置
     * -------------------------------------------------------------------------------------------------------------
     */
    public static void main(String[] args) {

        System.out.println("------------并查集测试------------");
        UnionFindSet unionFindSet = UniversalMethod.createUnionFindSet(Constant.UNION_FIND_SET_TEST);
        for (String equation: Constant.UNION_FIND_SET_TEST) {
            if (equation.charAt(1) == '!') {
                int p = equation.charAt(0) - 'a';
                int q = equation.charAt(3) - 'a';
                if (unionFindSet.find(p) == unionFindSet.find(q)) {
                    System.out.println(false);
                    return;
                }
            }
        }
        System.out.println(true);

    }
}